package Algorithm.dynamicProgramming.introduct;

/**
 * 122. 买卖股票的最佳时机 II https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
 * 题目简述：prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。计算所能获取的最大利润。
 */
public class MaxProfit2 {

    /**
     * 把股票的价格变化看作一个连续函数，在每个极小值点买入，在下一个极大值点卖出，则必能获得最大利润
     * 或者从贪心算法的角度来说，股票每一次上涨的利润都吃到，则必能获得最大利润
     */
    public int maxProfit(int[] prices) {
        int sumProfit = 0;
        for (int i = 1;i < prices.length;i++) {
            int profit = prices[i] - prices[i-1];
            //每一次上涨的利润都吃到
            if (profit > 0)
                sumProfit += profit;
        }
        return sumProfit;
    }

    /**
     * 动态规划
     * 1. 定义dp: dp[i][0]为第i天交易完后不持有股票最多现金，dp[i][1]为第i天交易完后持有股票最多现金
     * 2. 状态转移公式：第i天不持有股票这个状态可由第i-1天不持有股票或第i天卖出股票这两个状态得来，故dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
     *               第i天持有股票这个状态可由 第i-1天持有股票 或 第i-1天不持有股票且第i天买入股票 这两个状态得来，故dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
     * 3. 初始化：dp[0][0] = 0;dp[0][1] = -prices[0];
     * 4. 递推的过程中获取最大的dp[i][0]。
     *
     * 视频讲解：https://www.bilibili.com/video/BV1fM411B7tA
     */
    public int maxProfit2(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        int max = 0;
        for (int i = 1;i < prices.length;i++) {
            //若第i天不持有股票：可由 第i-1天不持有股票 或 第i天卖出股票 这两个状态得来
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            //若第i天持有股票：可由 第i-1天持有股票 或 第i-1天不持有股票且第i天买入股票 这两个状态得来
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
            //最后一定是不持有股票时的现金最多
            max = Math.max(max, dp[i][0]);
        }
        return max;
    }
}
